解题报告：P5569 [SDOI2008] 石子合并

发表于 分类于

题意

洛谷: link

给定 nn 堆石子（n≤40000n \le 40000），每次可以合并相邻的两堆石子，合并的收益为合并的两堆石子大小之和，求把所有石子合并为一堆可以获得的最大收益

暴力

如果 n≤4000n \le 4000 则可以使用区间 dp 解决，但是此题 nn 的范围过大，无法使用区间 dp

Garsia–Wachs 算法

oi-wiki 链接：link

算法流程

  1. 找到满足 vk−1<vk+1v_{k - 1} < v_{k + 1} 的最小的 kk
  2. 找到满足 vp>vk−1+vk, p<kv_p > v_{k - 1} + v_{k}, \ p < k 的最大的 pp
  3. 在 vv 中删除 vk−1,vkv_{k - 1}, v_{k}，在 pp 之后插入 vk−1+vkv_{k - 1} + v_k
  4. 在答案中累加 vk−1+vkv_{k - 1} + v_{k}

算法正确性的证明可以参考 oi-wiki

删除操作可以使用链表实现，由于本题数据较水，也可以使用 vector 暴力删除插入，开 O2 之后也可通过本题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
namespace solution
{
    typedef long long LL;
    const int MAXN = 40000 + 5;
    const LL INF = 0x3f3f3f3fLL;
    int n;
    LL a[MAXN];
    LL ans = 0;
    std::vector<LL> v;
    int find1()
    {
        for (int i = 1; i < v.size(); i++)
        {
            if (v[i - 1] < v[i + 1])
            {
                return i;
            }
        }
        return -1;
    }
    int find2(int x)
    {
        for (int i = x - 1; i >= 0; i--)
        {
            if (v[i] > v[x - 1] + v[x])
            {
                return i;
            }
        }
        return -1;
    }
    int main()
    {
        scanf("%d", &n);
        v.push_back(INF - 1);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            v.push_back(a[i]);
        }
        v.push_back(INF);

        for (int i = 1; i < n; i++)
        {
            LL p1 = find1();
            LL p2 = find2(p1);
            LL val = v[p1 - 1] + v[p1];
            v.erase(v.begin() + p1 - 1), v.erase(v.begin() + p1 - 1);
            v.insert(v.begin() + p2 + 1, val);
            ans += val;
        }

        printf("%lld\n", ans);
        return 0;
    }
}
int main()
{
    solution::main();
    return 0;
}